﻿/////////////////////////////////////////////////
//文件名:TrieTree
//描  述:
//创建者:刘凡平(Iveely Liu)
//邮  箱:945222889@qq.com
//组  织:Iveely
//年  份:2012/5/10 13:57:20
///////////////////////////////////////////////


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace IveelySE.BigData.Common.DataStruct
{
    /// <summary>
    /// 单词树
    /// </summary>
    public class TrieTree
    {
        /// <summary>
        /// 树结点
        /// </summary>
        public class Node
        {
            /// <summary>
            /// 所在层次
            /// </summary>
            public int Level { get; set; }

            /// <summary>
            /// 0-9的10个关键字
            /// </summary>
            public Key[] Keys = new Key[10];

            /// <summary>
            /// 构造方法
            /// </summary>
            /// <param name="level">结点所在层次</param>
            public Node(int level)
            {
                //实例化每一个关键字
                for (int i = 0; i < 10; i++)
                {
                    Keys[i] = new Key();
                }
                this.Level = level;
            }
            /// <summary>
            /// 关键字
            /// </summary>
            public class Key
            {
                /// <summary>
                /// 是否是一个值
                /// </summary>
                public bool isValue { get; set; }
                /// <summary>
                /// 子节点
                /// </summary>
                public Node child { get; set; }

                public Key()
                {
                    isValue = false;
                }
            }
        }

        /// <summary>
        /// 单例
        /// </summary>
        private static TrieTree fileTree = null;

        /// <summary>
        /// 根结点
        /// </summary>
        private Node Root = null;

        /// <summary>
        /// 获取实例（单例模式）
        /// </summary>
        /// <returns>返回实例</returns>
        public static TrieTree GetInstance()
        {
            if (fileTree != null)
            {
                return fileTree;
            }
            return fileTree = new TrieTree();
        }

        /// <summary>
        /// 构造方法
        /// </summary>
        private TrieTree()
        {
            Root = new Node(0);

        }




        private int[] ToArray(int value)
        {
            int val = value;
            int length = 0;
            do
            {
                val /= 10;
                length++;
            } while (val != 0);

            int[] array = new int[length];
            for (int i = 0; i < length; i++)
            {
                int temp = value % 10;
                value /= 10;
                array[i] = temp;
            }
            return array;
        }

        /// <summary>
        /// 插入值
        /// </summary>
        /// <param name="value">值</param>
        public void Add(int value)
        {
            //获取整数的位数
            int[] array = this.ToArray(value);
            Root = this.Add(0, array.Length, array, Root);
        }

        /// <summary>
        /// 插入值
        /// </summary>
        /// <param name="level">插入层次</param>
        /// <param name="length">总共插入长度</param>
        /// <param name="val">插入值（这是一个小于10的值）</param>
        /// <param name="node">插入结点</param>
        /// <returns>返回插入后的结点</returns>
        private Node Add(int level, int length, int[] val, Node node)
        {
            if (node.Keys[val[level]].child == null)
            {
                Node tempNode = new Node(level + 1);
                node.Keys[val[level]].child = tempNode;
                if (level + 1 == length)
                {
                    node.Keys[val[level]].isValue = true;
                }
            }
            if (level < length - 1)
            {
                node.Keys[val[level]].child = this.Add(level + 1, length, val, node.Keys[val[level]].child);

            }
            return node;
        }

        /// <summary>
        /// 判断是否在数中存在
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        public bool IsExist(int value)
        {
            int[] array = this.ToArray(value);
            Node temp = Root;
            bool flag = true;
            foreach (int a in array)
            {
                if (temp.Keys[a].child != null)
                {
                    flag = temp.Keys[a].isValue;
                    temp = temp.Keys[a].child;
                }
                else
                {
                    return false;
                }
            }
            return flag;
        }

        public void TestUse()
        {
            TrieTree ft = TrieTree.GetInstance();
            ft.Add(2012334);
            ft.Add(333232);
            ft.Add(4523423);
            Console.WriteLine(ft.IsExist(2012334));
            Console.WriteLine(ft.IsExist(201233));
            Console.WriteLine(ft.IsExist(8823843));
        }
    }
}
